package top100.backtrack;

import java.util.*;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/16 13:39
 * @description: 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 * <p>
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [4,6,7,7]
 * 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
 * 示例 2：
 * <p>
 * 输入：nums = [4,4,3,2,1]
 * 输出：[[4,4]]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 15
 * -100 <= nums[i] <= 100
 */
public class Solution491 {
    public void backtrack(int[] nums, int start, LinkedList<Integer> path, List<List<Integer>> res, boolean[] used) {
        if (start > nums.length) {
            return;
        }
        if (path.size() >= 2) {
            res.add(new ArrayList<>(path));
        }
        // 记录当前层级已使用的元素，用于去重
        Set<Integer> usedInCurrentLevel = new HashSet<>();

        for (int i = start; i < nums.length; i++) {
            if(usedInCurrentLevel.contains(nums[i])){
                continue;
            }
            if (path.isEmpty() || nums[i] >= path.getLast()) {
                path.addLast(nums[i]);
                usedInCurrentLevel.add(nums[i]);
                used[i] = true;
                backtrack(nums, i + 1, path, res, used);
                used[i] = false;
                path.removeLast();
            }
        }
    }

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, 0, new LinkedList<>(), res, used);
        return res;
    }

    public static void main(String[] args) {
        Solution491 solution = new Solution491();
        List<List<Integer>> res = solution.findSubsequences(new int[]{4, 6, 7, 7});
        System.out.println(res);
    }
}
